1. Technical Field
The present invention relates to computer networks in general and in particular to congestion management in computer networks.
2. Prior Art
Computer networks are an important mode for communicating and disseminating information. Network administrators are demanding more tools and features to enable profitable services. The tools and features should be simple to understand and implement.
Even though computer networks are diverse entities, a typical one includes end user terminals or workstations coupled by an infrastructure which includes transmission network and interconnecting devices. The transmission network may include transmission media such as optical fiber, wireless, wired, or similar communication media. The infrastructure may be as elaborate as the WWW (Worldwide Web) better known as the Internet or as simple as a local area network (LAN) using ethernet or token ring technology. The public switch telephone network is also an infrastructure for network users. The interconnecting devices, providing access to the transmission media, may include switches, routers, bridges, network interface cards (NICs), or similar devices.
A switch is a network node that directs datagrams on the basis of Medium Access Control (MAC) addresses, that is, Layer 2 in the OSI (Open System Interconnect) model well known to those skilled in the art. A switch can also be thought of as a multiport bridge, a bridge being a device that connects two Local Area Network (LAN) segments together and forwards packets on the basis of Layer 2 data.
A router is a network node that directs datagrams on the basis of finding the longest prefix in a routing table of prefixes that matches the Internet Protocol (IP) destination addresses of a datagram, all within Layer 3 in the OSI model. A Network Interface Card (NIC) is a device that interfaces a network such as the Internet with an edge resource such as a server, cluster of servers, or server farm. A NIC might classify traffic in both directions for the purpose of fulfilling Service Level Agreements (SLAs) regarding Quality of Service (QoS). A NIC may also enforce security policies. Security policies might include dropping packets classified as malicious or as inappropriately directed. Security policies might also include limiting the bandwidth of some flows during congestion, for example, during a Denial of Service attack.
In order to manage data and provide for Quality of Service (QoS) in said network devices, data packets are placed into pipes or flows. A flow control mechanism controls the rate at which data packets are moved from flows into a service queue for further servicing.
A common prior art flow control of packets in computer networks is called Random Early Detection (RED). This function is positioned to be effective as packets arrive. A packet is called transmitted if the decision of flow control is to enqueue it in a buffer to await processing. A packet is called discarded if the decision of flow control is to delete it. Queue occupancy can be expressed as a fraction of total capacity, so 0represents no packets awaiting processing and 1represents complete use of the buffer to store packets. As queue length in the buffer grows from 0to a threshold Lo>=0, RED at first transmits all packets into the queue. As queue occupancy exceeds Lo and increases further, a decreasing fraction of packets is transmitted into the queue. Finally, if occupancy reaches or exceeds a threshold Hi<=1, RED completely discards all arriving packets. In general 0<=Lo<=Hi<=1. The value of queue length in the buffer relative to these thresholds determines whether RED transmits or discards offered packets. For queue occupancy Q that is between Lo and Hi, the fraction T of packets transmitted can be a linear function of the following form:T(Q)=1−(1−Tmin)*(Q−Lo)/(Hi−Lo); where * represents multiplication operator.Here Tmin is a minimum transmitted fraction reached as Q increases to Hi. Many variations on this theme are practiced in the prior art; for example, Q might actually be an exponentially weighted moving average of queue occupancy. As another example, Lo=Hi, the special case known as taildrop flow control. That is, taildrop flow control calls for transmitting all packets if Q is less than Lo=Hi, otherwise transmitting no packets.
The use of multiple thresholds (weights) is called Weighted RED (WRED).
The use of RED or WRED (including many variants) unfortunately can imply some undesirable consequences including:
1. RED and WRED ignore rate of change of queue (queue going up, down)
2. High thresholds can cause high latency and lack of headroom for bursts
3. Low thresholds can cause burst-shaving (low utilization)
4. There is no direct relationship between thresholds and performance
5. Administrative input can be needed to retune thresholds as offered loads change
6. Hand-tuning thresholds is widely recognized as difficult
7. Little or no guidance appears in vendor documents.
8. Bandwidth allocation for hierarchies of bandwidth limits cannot be easily provided
9. Bandwidth allocation that respects piority cannot be easily provided.
A drawback of prior art techniques is that the decision to transmit or discard an arriving packet is made in the device based upon heuristically determined threshold or functions. A queue threshold has little or nothing to do with key characteristics of flows. Threshold flow control systems can also be subject to high queueing latency during even a small degree of oversubscription.
In view of the above RED or WRED does not give a network administrator sufficient control to manage a computer network efficiently. As a consequence a system and method are required to provide the necessary control.